import javafx.util.Pair;

import java.util.*;
public class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    public void reorderList(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) return;
        ListNode head1 = head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //ListNode head2 = new ListNode(-1);
        ListNode head2 = null;
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            //cur.next = head2.next;
            cur.next = head2;
            head2 = cur;
            //head2.next = cur;
            cur = next;
        }
        ListNode cur1 = head1;
        //ListNode cur2 = head2.next;
        ListNode cur2 = head2;
        //ListNode prev = new ListNode(-1);
        // while(cur1 != null){
        //     prev.next = cur1;
        //     prev = cur1;
        //     cur1 = cur1.next;
        //     if(cur2 != null){
        //         prev.next = cur2;
        //         prev = cur2;
        //         cur2 = cur2.next;
        //     }
        // }
        while (cur1 != null && cur2 != null) {
            ListNode next1 = cur1.next;
            ListNode next2 = cur2.next;
            cur1.next = cur2;
            cur2.next = next1;
            cur1 = next1;
            cur2 = next2;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        int n = len / k;
        if (n == 0) return head;
        ListNode newhead = new ListNode(-1);
        ListNode prev = newhead;
        cur = head;
        for (int i = 0; i < n; i++) {
            ListNode tmp = cur;
            int count = k;
            while (count-- > 0) {
                ListNode next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev.next = cur;
        return newhead.next;
    }

    /*    public int[] twoSum(int[] nums, int target) {
            int left = 0;
            int right = 1;
            int n = nums.length;
            int[] ret = new int[2];
            while(right < n){
                if(nums[left] + nums[right] > target){
                    left++;
                }else if(nums[left] + nums[right] < target){
                    right++;
                }else{
                    ret[0] = left;
                    ret[1] = right;
                    break;
                }
                if(left == right)right++;
            }
            return ret;
        }*/
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] hash = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s1.length(); i++) {
            int a = --hash[s2.charAt(i) - 'a'];
            if (a < 0) return false;
        }
        return true;
    }

    public String longestCommonPrefix(String[] strs) {
        int ret = Integer.MAX_VALUE;
        for (int j = 0; j < strs.length; j++) {
            int i = 0;
            char[] s1 = strs[0].toCharArray();
            char[] s2 = strs[j].toCharArray();
            int len = Math.min(strs[0].length(), strs[j].length());
            while (i < len) {
                if (s1[i] == s2[i]) i++;
                else {
                    while (s1[i] == s2[i]) {
                        i--;
                    }
                    len = i;
                    break;
                }
            }
            ret = Math.min(ret, i);
        }
        return ret < 0 ? new String() : new String(strs[0].substring(0, ret));
    }

    public String longestPalindrome(String s) {
        int n = s.length();
        int len = 1;
        int begin = 0;
        for (int i = 0; i < n; i++) {
            int left = i;
            int right = i;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (len < right - left - 1) {
                len = right - left - 1;
                begin = left + 1;
            }
            left = i;
            right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (len < right - left - 1) {
                len = right - left - 1;
                begin = left + 1;
            }
        }
        return s.substring(begin, begin + len);
    }

    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        boolean flag = true;
        StringBuilder ret = new StringBuilder();
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        int[] tmp = new int[m + n - 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                if (tmp[i + j] != 0) flag = false;
            }
        }
        if (flag) return "0";
        int k = 0;
        int sum = 0;
        while (k < m + n - 1 || sum != 0) {
            if (k < m + n - 1) sum += tmp[k++];
            ret.append(sum % 10);
            sum /= 10;
        }
        return ret.reverse().toString();
    }

    public String removeDuplicates(String s) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (str.length() > 0 && str.toString().charAt(str.length() - 1) == s.charAt(i)) {
                str.deleteCharAt(str.length() - 1);
            } else {
                str.append(s.charAt(i));
            }
        }
        return str.toString();
    }

    public int calculate(String _s) {
        char op = '+';
        int ret = 0;
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int n = _s.length();
        char[] s = _s.toCharArray();
        while (i < n) {
            if (s[i] == ' ')
                i++;
            else if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                switch (op) {
                    case '+':
                        stack.push(tmp);
                        break;
                    case '-':
                        stack.push(-tmp);
                        break;
                    case '*':
                        stack.push(stack.pop() * tmp);
                        break;
                    case '/':
                        stack.push(stack.pop() / tmp);
                        break;
                }
                ;
            } else {
                op = s[i];
                i++;
            }
        }
        while (!stack.isEmpty())
            ret += stack.pop();
        return ret;
    }

    public String decodeString(String _s) {
        Stack<String> str = new Stack<>();
        str.push("");
        Stack<Integer> num = new Stack<>();
        int i = 0, n = _s.length();
        char[] c = _s.toCharArray();
        while (i < n) {
            if (c[i] == '[') {
                StringBuilder s = new StringBuilder();
                i++;
                while (i < n && c[i] >= 'a' && c[i] <= 'z') {
                    s.append(c[i]);
                    i++;
                }
                str.push(s.toString());
            } else if (c[i] == ']') {
                String s1 = str.pop();
                String s2 = new String();
                int m = num.pop();
                for (int j = 0; j < m; j++) {
                    s2 += s1;
                }
                str.push(str.pop() + s2);
                i++;
            } else if (c[i] >= '0' && c[i] <= '9') {
                int tmp = 0;
                while (i < n && c[i] >= '0' && c[i] <= '9') {
                    tmp = tmp * 10 + (c[i] - '0');
                    i++;
                }
                num.push(tmp);
            } else {
                String s1 = str.pop();
                StringBuilder s = new StringBuilder();
                while (i < n && c[i] >= 'a' && c[i] <= 'z') {
                    s.append(c[i]);
                    i++;
                }
                str.push(s1 + s.toString());
            }
        }
        return str.pop();
    }

    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int n = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                Node t = q.poll();
                tmp.add(t.val);
                for (Node child : t.children) {
                    if (child != null) q.offer(child);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null)return ret;
        Queue<TreeNode> q = new LinkedList<>();
        boolean flag = true;
        q.offer(root);
        while(!q.isEmpty()){
            int n = q.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i < n;i++){
                TreeNode cur = q.poll();
                if(flag)list.add(cur.val);
                else list.add(0,cur.val);
                if(cur.left != null)q.offer(cur.left);
                if(cur.right != null)q.offer(cur.right);
            }
            ret.add(list);
            if(flag)flag = false;
            else flag = true;
        }
        return ret;
    }
/*    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        for(String str : words){
            map.put(str,map.getOrDefault(str,0) + 1);
        }
        PriorityQueue<Pair<String,Integer>> q = new PriorityQueue<>(
                (a,b) -> {
                    if(a.getValue().equals(b.getValue())){
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue() - b.getValue();
                }
        );
        for(Map.Entry<String,Integer> n : map.entrySet()){
            q.offer(new Pair<>(n.getKey(),n.getValue()));
            if(q.size() > k){
                q.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while(!q.isEmpty()){
            ret.add(q.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }*/
    public int minMutation(String startGene, String endGene, String[] bank) {
        char[] ch = { 'A', 'C', 'G', 'T' };
        HashSet<String> vis = new HashSet<>();
        HashSet<String> set = new HashSet<>();
        for (String str : bank)set.add(str);
        if (!set.contains(endGene))return -1;
        if (startGene.equals(endGene))return 0;
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);
        int ret = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            ret++;
            for (int i = 0; i < sz; i++) {
                String t = q.poll();
                for (int j = 0; j < 8; j++) {
                    char[] tmp = t.toCharArray();
                    for (int k = 0; k < 4; k++) {
                        tmp[j] = ch[k];
                        String next = new String(tmp);
                        if(next.equals(endGene))return ret;
                        if(set.contains(next) && !vis.contains(next)){
                            vis.add(new String(tmp));
                            q.offer(new String(tmp));
                        }
                    }
                }
            }
        }
        return -1;
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> vis = new HashSet<>();
        HashSet<String> set = new HashSet<>();
        for (String str : wordList)
            set.add(str);
        if (!set.contains(endWord))
            return 0;
        int ret = 1;
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        while (!q.isEmpty()) {
            int sz = q.size();
            ret++;
            for (int i = 0; i < sz; i++) {
                String t = q.poll();
                for (String s : set) {
                    int count = 0;
                    for (int j = 0; j < s.length(); j++) {
                        if (t.charAt(j) != s.charAt(j))
                            count++;
                    }
                    if (count <= 1) {
                        if (s.equals(endWord))
                            return ret;
                        if (!vis.contains(s)){
                            q.offer(s);
                            vis.add(s);
                        }
                    }
                }
            }
        }
        return 0;
    }
    Map<Character, Set<Character>> edges = new HashMap<>();
    Map<Character, Integer> in = new HashMap<>();
    boolean check;
    public void add(String s1,String s2){
        int m = Math.min(s1.length(),s2.length());
        int i = 0;
        for(;i < m;i++){
            char c1 = s1.charAt(i),c2 = s2.charAt(i);
            if(c1 != c2){
                if(!edges.containsKey(c1)){
                    edges.put(c1,new HashSet<>());
                }
                if(!edges.get(c1).contains(c2)){
                    edges.get(c1).add(c2);
                    in.put(c2,in.get(c2) + 1);
                }
                break;
            }
        }
        if(i == s2.length() && i < s1.length())check = true;
    }
    public String alienOrder(String[] words) {
        for(String s : words){
            for(int i = 0;i < s.length();i++){
                in.put(s.charAt(i),0);
            }
        }
        for(int i = 0;i < words.length;i++){
            for(int j = i + 1;j < words.length;j++){
                add(words[i],words[j]);
                if(check)return "";
            }
        }
        Queue<Character> q = new LinkedList<>();
        for(char ch : in.keySet()){
            if(in.get(ch) == 0)q.add(ch);
        }
        StringBuilder ret = new StringBuilder();
        while(!q.isEmpty()){
            char t = q.poll();
            ret.append(t);
            if(!edges.containsKey(t))continue;
            for(char ch : edges.get(t)){
                in.put(ch,in.get(ch) - 1);
                if(in.get(ch) == 0)q.add(ch);
            }
        }
        for(char ch : in.keySet()){
            if(in.get(ch) != 0)return "";
        }
        return ret.toString();
    }
    public boolean lemonadeChange(int[] bills) {
        int[] in = new int[2];
        for(int i = 0;i < bills.length;i++){
            if(bills[i] == 5)in[0]++;
            else if(bills[i] == 10){
                if(in[0] > 0){
                    in[0]--;
                    in[1]++;
                }else return false;
            }else{
                if(in[0] > 0 && in[1] > 0){
                    in[0]--;
                    in[1]--;
                }else if(in[0] > 2){
                    in[0] -= 2;
                }else return false;
            }
        }
        return true;
    }
/*    public String[] sortPeople(String[] names, int[] heights) {
        PriorityQueue<Pair<String,Integer>> q = new PriorityQueue<>((a,b) -> b.getValue() - a.getValue());
        for(int i = 0;i < names.length;i++){
            q.add(new Pair<>(names[i],heights[i]));
        }
        String[] ret = new String[names.length];
        for(int i = 0;i < names.length;i++){
            Pair<String,Integer> t = q.poll();
            ret[i] = t.getKey();
        }
        return ret;
    }*/
    public int maxSumDivThree(int[] nums) {
        int ret = 0;
//        int y1 = Integer.MAX_VALUE;
//        int y2 = Integer.MAX_VALUE;
//        int x1 = Integer.MAX_VALUE;
//        int x2 = Integer.MAX_VALUE;
         int y1 = 0x3f3f3f3f;
         int y2 = 0x3f3f3f3f;
         int x1 = 0x3f3f3f3f;
         int x2 = 0x3f3f3f3f;
        for (int x : nums) {
            ret += x;
            if (x % 3 == 1) {
                if (x1 > x) {
                    x2 = x1;
                    x1 = x;
                } else if (x2 > x) {
                    x2 = x;
                }
            }
            else if (x % 3 == 2) {
                if (y1 > x) {
                    y2 = y1;
                    y1 = x;
                } else if (y2 > x) {
                    y2 = x;
                }
            }
        }
        if (ret % 3 == 0)
            return ret;
        else if (ret % 3 == 1)
            return Math.max(ret - x1, ret - y1 - y2);
        else
            return Math.max(ret - y1, ret - x1 - x2);
    }
    public static void main154(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        Integer[] in = new Integer[n];
        for(int i = 0;i < n;i++){
            nums[i] = scan.nextInt();
            in[i] = i;
        }
        Arrays.sort(in,(i,j) -> nums[j] - nums[i]);
        int mid = nums[in[n / 2]];
        int[] ret = new int[n];
        for(int i = 0;i < n;i++){
            if(nums[in[i]] >= mid){
                ret[in[i]] = 0;
            }else{
                ret[in[i]] = mid - nums[in[i]] + 1;
            }
        }
        for(int i : ret){
            System.out.print(i);
            System.out.print(' ');
        }
        scan.close();
    }

    public static void main4658(String[] args) {
        Scanner scan = new Scanner(System.in);
        long k = scan.nextLong();
        if(k > 4){
            System.out.println(-1);
            return;
        }
        long ret = 1;
        long count = 0;
        long i = 1;
        while(k > 0){
            ret *= i;
            if(ret % 10 == 0){
                ret /= 10;
                count++;
                k--;
            }

        }
        for(int j = 0;j < count;j++)ret *= 10;
        System.out.println(ret);
        scan.close();
    }
    public static void main16541651(String[] args) {
        long mod = 1000000007;
        long ret = 1;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] in = new int[n];
        for(int i = 0;i < n;i++)in[i] = scan.nextInt();
        Arrays.sort(in);
        List<List<Integer>> l = new ArrayList<>();
        int[] nums = new int[10];
        int num = 0;
        int max = 0;
        for(int i :in){
            nums[i]++;
            if(nums[i] > max){
                max = nums[i];
            }
        }
        for(int i = 0;i < max;i++)l.add(new ArrayList<>());
        max = 0;
        for(int i = 0;i < n;i++){
            if(num == in[i]){
                l.get(max++).add(in[i]);
            }else{
                num = in[i];
                max = 0;
                l.get(max++).add(in[i]);
            }
        }
        for(int i = 0;i < l.size();i++){
            int len = 1;
            for(int j = 1;j < l.get(i).size();j++){
                if(l.get(i).get(j) - 1 == l.get(i).get(j - 1)){
                    len++;
                }
            }
            ret *= (len == l.get(i).size() ? l.get(i).size() + 1 : len - 1);
            ret %= mod;
        }
        System.out.println(ret);
        scan.close();
    }
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};
    public static char[][] ret;
    public static int m,n;
    public static boolean[][] vis;
    public static void main134531(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        char[] ch = scan.next().toCharArray();
        int up = 1,down = 1,left = 1,right = 1;
        for(char c : ch){
            if(c == 'U'){
                up++;
            }else if(c == 'D'){
                down++;
            }else if(c == 'L'){
                left++;
            }else if(c == 'R'){
                right++;
            }
        }
        m = 2*(Math.max(up,down) + 2);
        n = 2*(Math.max(left,right) + 2);
        ret = new char[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                ret[i][j] = '.';
            }
        }
        int x = Math.max(up,down);
        int y = Math.max(left,right);
        vis = new boolean[m][n];
        ret[x][y] = ' ';
        for(char c : ch){
            if(c == 'U'){
                x++;
                ret[x][y] = ' ';
            }else if(c == 'D'){
                x--;
                ret[x][y] = ' ';
            }else if(c == 'L'){
                y++;
                ret[x][y] = ' ';
            }else if(c == 'R'){
                y--;
                ret[x][y] = ' ';
            }
        }
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++){
                if(ret[i][j] == ' '){
                    dfs(i,j);
                }
            }
        int start = -1,end = -1;
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++){
                if(ret[i][j] == '*' && start == -1){
                    start = i;
                }else if(ret[i][j] == '*'){
                    end = i;
                }
            }
        for(int i = start + 1;i < end;i++)
            for(int j = 0;j < n;j++){
                if(ret[i][j] == '.' && ret[i + 1][j] == '*' && ret[i - 1][j] == '*' && ret[i][j + 1] == '*' && ret[i][j - 1] == '*'){
                    ret[i][j] = '*';
                }
            }
        for(int i = 0;i < m;i++){
            boolean flag = false;
            if(i == start || i == end)System.out.print(' ');
            for(int j = 0;j < n;j++){
                if(ret[i][j] == ' ' || ret[i][j] == '*'){
                    System.out.print(ret[i][j]);
                    flag = true;
                }
            }
            if(i == start || i == end)System.out.print(' ');
            if(flag)System.out.println();
        }
        scan.close();
    }
    public static void dfs(int i,int j){
        for(int k = 0;k < 4;k++){
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == '.'){
                ret[x][y] = '*';
            }
        }
    }

    public static void main4758(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        HashMap<Character,Integer> map = new HashMap<>();
        PriorityQueue<Character> q = new PriorityQueue<>((a,b) -> {
            if(a == b){
                return map.get(b) - map.get(a);
            }else{
                return a - b;
            }
        });
        for(char c : str.toCharArray())map.put(c , map.getOrDefault(c,0) + 1);
        for(char c : map.keySet())q.add(c);
        int n = q.size();
        int count = map.get(q.peek());
        for(int i = 0;i < n;i++){
            char c = q.poll();
            if(count == map.get(c))
                System.out.print(c);
        }
        scan.close();
    }
    public static void mainasgd(String[] args) {
        /**
         * 第一行包含一个正整数 N。
         * 第二行包含 N 个整数：A1, A2, A3, . . . , AN.
         */
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        //对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题
        //比他多的学生数不超过刷题比他少的学生数。
        int[] copyarr = Arrays.copyOfRange(arr, 0, arr.length);
        //将新的复制数组进行排序
        Arrays.sort(copyarr);
        int median = copyarr[copyarr.length/2];
        int result[] = new int[arr.length];

        int lage = 0;//是否加1的控制开关 默认不加
        int bigger = 0;
        int smaller = 0;
        int mid = 0;
        //找出比中间值大的数有多少 比中间值小的数有多少
        for (int i = 0; i < arr.length; i++) {
            if(copyarr[i]>median) {
                bigger++;
            }else if(copyarr[i]<median) {
                smaller++;
            }
        }

        if(bigger>=smaller) {
            lage = 1;
        }

        if(bigger>smaller) {
            mid=1;
        }

        for (int i = 0; i < result.length; i++) {
            if(arr[i]< median) {
                result[i] = median+lage - arr[i];
            }else if(arr[i]==median&&mid==1) {
                result[i] = median+mid-arr[i];
            }else{
                result[i] = 0;
            }
        }
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+" ");
        }
    }
    private static class Pair {
        int x1, x2;
        long num;
        public Pair(int x1, int x2,long num) {
            this.x1 = x1;
            this.x2 = x2;
            this.num = num;
        }

        public int getKey() {
            return x1;
        }

        public int getValue() {
            return x2;
        }
    }

    public static void main(String[] args) {
        List<Pair> l = new ArrayList<>();
        l.add(new Pair(1,2,3l));
        System.out.println(l.get(0).getKey());
    }
}